package leetcode.每日一题;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @author ：zsy
 * @date ：Created 2022/11/9 9:37 PM
 * @description：
 */
public class 最大加号标志 {
    @Test
    public void test() {
        System.out.println(new Solution().orderOfLargestPlusSign(5, new int[][]{{4, 2}}));
    }

    class Solution {
        public int orderOfLargestPlusSign(int n, int[][] mines) {
            int[][] gap = new int[n + 2][n + 2];
            for (int[] g : gap) {
                Arrays.fill(g, 1);
            }
            for (int[] mine : mines) {
                gap[mine[0] + 1][mine[1] + 1] = 0;
            }
            int[][] a = new int[n + 2][n + 2]; // 右
            int[][] b = new int[n + 2][n + 2]; // 下
            int[][] c = new int[n + 2][n + 2]; // 上
            int[][] d = new int[n + 2][n + 2]; // 左
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (gap[i][j] == 1) {
                        a[i][j] = a[i][j - 1] + 1;
                        b[i][j] = b[i -1][j] + 1;
                    }
                    if (gap[n + 1 - i][n + 1 - j] == 1) {
                        c[n + 1 - i][n + 1 - j] = c[n + 2 - i][n + 1 - j] + 1;
                        d[n + 1 - i][n + 1 - j] = d[n + 1 - i][n + 2 - j] + 1;
                    }
                }
            }
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    ans = Math.max(ans, Math.min(Math.min(a[i][j], b[i][j]), Math.min(c[i][j], d[i][j])));
                }
            }
            return ans;
        }
    }
    /*class Solution {
        public int orderOfLargestPlusSign(int n, int[][] mines) {
            int[][] gap = new int[n][n];
            for (int[] mine : mines) {
                gap[mine[0]][mine[1]] = 1;
            }
            int ans = 0;

            return ans;
        }

        private int[][] dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

        private int dfs(int i, int j, int[][] gap) {
            int n = gap.length;
            if (gap[i][j] == 1) return 0;
            int ans = 1;
            Queue<int[]> queue = new LinkedList<>();
            for (int[] dir : dirs) {
                queue.offer(new int[]{i + dir[0], j + dir[1]});
            }
            while (true) {
                int size = queue.size();
                for (int k = 0; k < size; k++) {
                    int[] cur = queue.poll();
                    int x = cur[0];
                    int y = cur[1];
                    if (x < 0 || x >= n
                            || y < 0 || y >= n
                            || gap[x][y] == 1) {
                        return ans;
                    }
                    queue.offer(new int[]{x + dirs[k][0], y + dirs[k][1]});
                }
                ans++;
            }
        }
    }*/
}
